#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

size_t str_len(char* str) {
  size_t len = 0;
  while (*str++ != '\0') {
    len++;
  }
  return len;
}

char* reverse_str(char* str, size_t start, size_t end) {
  while (start < end) {
    iter_swap(str + start++, str + end--);
  }
  return str;
}

char* reverse_word(char* str) {
  // reverse the whole sentence
  size_t len = str_len(str);
  reverse_str(str, 0, len-1);

  // reverse each word
  size_t start = 0;
  size_t end = 0;
  while (end < len) {
    if (str[end] != ' ') {
      start = end;
      while (end < len && str[end] != ' ')
	end++;
      reverse_str(str, start, --end);
    }
    end++;
  }

  return str;
}

char first_nonrepeated(char* const str) {
  if (str) {
    vector<size_t> repeat(1 << 8, 0);
    for (char* p = str; *p != '\0'; p++) {
      repeat[(size_t) *p]++;
    }

    for (char* p = str; *p != '\0'; p++) {
      if (repeat[(size_t) *p] == 1)
	return *p;
    }
  }
  return '\0';
}

int str_to_int(char* str) {
  if (!str)
    throw "Null string";

  bool neg = false;
  if (*str == '-') {
    neg = true;
    str++;
  }

  int num = 0;
  while (*str != '\0') {
    num = num * 10 + (*str - '0');
    str++;
  }

  return neg ? num * (-1) : num;
}

char* int_to_str(int num) {
  const size_t MaxDigit = 10;
  char* str = new char[MaxDigit+2];
  memset(str, 0, sizeof(MaxDigit+2));
  
  bool neg = false;
  if (num < 0) {
    neg = true;
    num *= -1;
  }

  char* p = str;
  do {
    int digit = num % 10;
    *p++ = '0' + digit;
    num /= 10;
  } while (num);

  if (neg)
    *p = '-';

  return reverse_str(str, 0, str_len(str)-1);
}

char* shitleft(char* str, size_t offset) {
  if (!str)
    throw "Invalid params";

  size_t len = str_len(str);
  offset = offset % len;

  reverse_str(str, 0, len-1);
  reverse_str(str, 0, len-1-offset);
  reverse_str(str, len-offset, len-1);

  return str;
}

char* delete_chars(char* str, char* chars) {
  if (!str || !chars) 
    throw "Invalid params";

  vector<bool> should_delete(1 << 8, false);
  while (*chars != '\0') {
    should_delete[(size_t) *chars++] = true;
  }

  char* open = str;
  char* curr = str;
  while (*curr != '\0') {
    if (!should_delete[(size_t) *curr]) {
      iter_swap(open++, curr);
    }
    curr++;
  }

  while (*open != '\0') {
    *open++ = '\0';
  }
  
  return str;
}

size_t max_symmetrical_len(const char* str) {
  size_t max_len = 0;
  if (str) {
    const char* iter = str;
    while (*iter != '\0') {
      // odd length
      const char* left = iter-1;
      const char* right = iter+1;
      while (left >= str && *right != '\0' && *left == *right) {
	left--, right++;
      }
      max_len = max<size_t>(max_len, right - left - 1);

      // even length
      if (*iter == *(iter+1)) {
	left = iter-1;
	right = iter+2;
	while (left >= str && *right != '\0' && *left == *right) {
	  left--, right++;
	}
	max_len = max<size_t>(max_len, right - left - 1);
      }

      iter++;
    }
  }
  return max_len;
}

int main() {
  char t[] = "zhifeng sun is here";
  size_t len = str_len(t);
  cout << "Testing str len: " << len << endl;
  cout << "Testing reverse: " << reverse_str(t, 0, len-1) << endl;
  cout << "Still testing reverse: " << reverse_str(t, 0, len-1) << endl;
  cout << "Testing reverse words: " << reverse_word(t) << endl;
  cout << "Testing reverse words: " << reverse_word(t) << endl;

  cout << "Testing first non-repeated: " << first_nonrepeated("abaccdeff") << endl;
  cout << "Testing first non-repeated: " << first_nonrepeated("aaabbb") << endl;

  cout << "Testing str-to-int: " << str_to_int("123") << endl;
  cout << "Testing str-to-int: " << str_to_int("-1") << endl;
  cout << "Testing str-to-int: " << str_to_int("0") << endl;

  cout << "Testing int-to-str: " << int_to_str(123) << endl;
  cout << "Testing int-to-str: " << int_to_str(-1) << endl;
  cout << "Testing int-to-str: " << int_to_str(0) << endl;
  cout << "Testing int-to-str: " << int_to_str(-0) << endl;

  cout << "Testing shitleft: " << shitleft(t, 0) << endl;
  cout << "Testing shitleft: " << shitleft(t, 1) << endl;
  cout << "Testing shitleft: " << shitleft(t, 6) << endl;
  
  cout << "Testing delete chars: " << delete_chars(t, "aeiou") << endl;

  cout << "Testing max symmetrical length: " << max_symmetrical_len("google") << endl;
  cout << "Testing max symmetrical length: " << max_symmetrical_len("goooooog") << endl;
  return 0;
}
